#include "BTNode.hpp"
#ifndef _BTREE_HPP_
#define _BTREE_HPP_

template <typename T> class BTree {
public:
	BTree (int order = 3): _order(order), _size(0) {
		_root = new BTNode<T>();
	}
	~BTree() {
		if(_root) {
			release(_root);
		}
	}

	int order() const { return _order; }
	int size() const { return _size; }
	BTNodePosi(T) &root() { return _root; }
	bool empty() const { return !_root; }

	/* search by level */
	BTNodePosi(T) search(const T &e) {
		BTNodePosi(T) v = _root;
		_hot = NULL;
		while(v) {
			/* Find the highest position of an element not greater than e. */
			int r = v->key.size();
			for(r -= 1;r >= 0; --r) {
				if(v->key[r] <= e) break;
			}

			if(0 <= r && e == v->key[r]) return v;
			_hot = v;
			v = v->child[r + 1];
		}
		return NULL;
	}

	bool insert(const T &e) {
		BTNodePosi(T) v = search(e);
		if(v) return false;

		int r = _hot->key.size();
		for(r -= 1; r >= 0; --r) {
			if(_hot->key[r] <= e) break;
		}
		_hot->key.insert(_hot->key.begin() + (r + 1), e);
		_hot->child.insert(_hot->child.begin() + (r + 2), NULL);
		++_size;
		/* if needed, make an overflow operation. */
		solveOverflow(_hot);
		return true;
	}
	bool remove(const T &e) {
		BTNodePosi(T) v = search(e);
		if(!v) return false;

		int r = v->key.size();
		for(r -= 1; r >= 0; --r) {
			if(v->key[r] <= e) {
				break;
			}
		}
		
		/* make sure the node v is at the bottom. */
		if(v->child[0]) {
			BTNodePosi(T) u = v->child[r + 1];
			/* find the successor of e. */
			while(u->child[0]) u = u->child[0];

			/* use "u" instead of "v" */
			v->key[r] = u->key[0];
			v = u;
			r = 0;
		}
		v->key.erase(v->key.begin() + r);
		v->child.erase(v->child.begin() + r + 1);
		--_size;

		solveUnderflow(v);
		return true;
	}
protected:
	int _size; /* the size of key words. */
	int _order; /* the order of B- three */
	BTNodePosi(T) _root;
	BTNodePosi(T) _hot;

	/* _size and _order satisfy: _size + 1 <= _order */
	void solveOverflow(BTNodePosi(T)) {
		/* recursive base: the current node does not overflow. */
		if(_order >= v->child.size()) return; 

		/**
		 * @brief 
		 * for key:
		 * 0, 1, 2, 3, _order=4, --> s=2
		 * 0, 1, 2, 3, 4, _order=5, --> s=2
		 * 3 parts: s, 1, _order - s - 1.
		 * 
		 */
		int s = _order / 2;
		/* !Note: u->child.size() == 1 */
		/* u is the large part! */
		BTNodePosi u = new BTNode<T>();
		/* move the key of v to u. */
		/* u has _order - s - 1 key nodes. */
		u->key.assign(v->key.begin() + s + 1, v->key.end());
		/* move the child of v to u */
		/* u has (_order - s) key nodes. */
		u->child.insert(u->child.begin(), 
			v->child.begin() + s + 1, 
			v->child.end() - 1);
		u->child[_order - s - 1] = v->child[_order - 1];
		/* erase elements deleted. */
		v->key.erase(v->key.begin() + s + 1, v->key.end());
		v->child.erase(v->child.begin() + s + 1, v->child.end());

		/* Use "...->child" to check whether a child node exists. */
		/* If the child node of u is not empty, change the parent node of the child nodes. */
		if(u->child[0]) {
			for (int j = 0; j < _order - s; ++j) {
				u->child[j]->parent = u;
			}
		}

		BTNodePosi p = v->parent;
		/* If p is null, create a BTNode. */
		if(!p) {
			_root = p = new BTNode<T>();
			p->child[0] = v;
			v->parent = p;
		}
		/* The code below is so subtle that it prevents r from being less than 0. */
		/* find a key such that p->key[r] <= v->key[0]. */
		int r = p->key.size();
		for (r -= 1; r >= 0; --r) {
			if(p->key[r] <= v->key[0]) break;
		}
		/* the position of u in p */
		++r;

		p->key.insert(p->key.begin() + r, v->key[s]);
		v->key.erase(v->key.begin() + s);
		p->child.insert(v->child.begin() + 1 + r, u);
		u->parent = p;
		solveOverflow(p);
	}

	void solveUnderflow(BTNodePosi(T) v) {
		if((_order + 1) / 2 <= v->child.size()) return;

		BTNodePosi(T)p = v->parent;
		if(!p) {
			if(!v->key.size() && v->child[0]) {
				_root = v->child[0];
				v->child[0] = nullptr;
				release(v);
			}
			return;
		}

		int r = 0;
		while(p->child[r] != v) r++;

		/* There is at least one left brother. */
		if(0 < r) {
			BTNodePosi(T) ls = p->child[r-1];
			/* The left brother has enough child. */
			/* left -> p -> v */
			if((_order + 1)/2 < ls->child.size()) {
				v->key.insert(v->key.begin(), p->key[r-1]);

				p->key[r-1] = ls->key.back();
				ls->key.erase(ls->key.end() - 1);

				v->child.insert(v->child.begin(), ls->child.back());
				ls->child.erase(ls->child.end() - 1);

				if(v->child[0]) v->child[0]->parent = v;
				return;
			}
		}

		/* There is at least one right brother. */
		if(p->child.size() - 1 > r) {
			BTNodePosi(T) rs = p->child[r+1];

			/* The right brother has enough child. */
			/* v -> p -> right */
			if((_order + 1)/2 < rs->child.size()) {
				v->key.insert(v->key.end(), p->key[r]);

				p->key[r] = rs->key[0];
				rs->key.erase(rs->key.begin());

				v->child.insert(v->child.end(), rs->child[0]);
				rs->child.erase(rs->child.begin());

				if(v->child.back()) v->child.back()->parent = p;
				return;
			}
		}

		/* merge with left brother. */
		if(0 < r) {
			BTNodePosi(T) ls = p->child[r-1];
			
			ls->key.insert(ls->key.end(), p->key[r-1]);
			p->key.erase(p->key.begin() + r - 1);
			p->child.erase(p->child.begin() + r);
			
			ls->key.insert(ls->key.end(), v->key.begin(), v->key.end());

			int ls_end = ls->child.size();
			ls->child.insert(ls->child.end(), v->child.begin(), v->child.end());
			for(; ls_end < ls->child.size(); ls_end++) {
				if(ls->child[ls_end]) {
					ls->child[ls_end]->parent = ls;
				}
			}
			release(v);
		}

		else {
			BTNodePosi(T) rs = p->child[r+1];
			rs->key.insert(rs->key.begin(), p->key[r]);
			p->key.erase(p->key.begin() + r);
			p->child.erase(p->child.begin() + r);

			rs->key.insert(rs->key.begin(), v->key.begin(), v->key.end());

			int v_end = v->child.size();
			rs->child.insert(rs->child.begin(), v->child.begin(), v->child.end());
			for(int i = 0; i < v_end; i++) {
				if(rs->child[i]) {
					rs->child[i]->parent = rs;
				}
			}
			release(v);
		}

		solveUnderflow(p);
	}

};

#endif